package 中等.动态规划.数组区间;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 给你一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 difference 。
 * <p>
 * 子序列 是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-arithmetic-subsequence-of-given-difference
 */
public class 最长定差子序列_1218 {

    public static void main(String[] args) {
        int[] arr = {16, -4, -6, -11, -8, -9, 4, -11, 15, 15, -9, 11, 7, -7, 10, -16, 4};
        System.out.println(longestSubsequence(arr, 3));

    }

    /**
     * 动态规划
     * 1，子问题：
     * 以i元素结尾的最长等差子序列的长度是多少
     * 2，递推关系
     * 当前i元素的最长等差子序列长度=
     * 如果存在[0，i-1]之间的某个元素相差difference
     * 那么   dp[i]=dp[j]+1，否则，dp[i]=1
     * 3，顺序
     * 顺序推导
     *
     * @param arr
     * @param difference
     * @return
     */
    public static int longestSubsequence(int[] arr, int difference) {
        int[] dp = new int[arr.length];
        Arrays.fill(dp, 1);
        int max = 1;
        for (int i = 1; i < arr.length; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (arr[i] - arr[j] == difference) {
                    dp[i] = dp[j] + 1;
                    max = Math.max(max, dp[i]);
                    break;
                }
            }
        }
        return max;
    }

    /**
     * 空间优化
     * 可以利用哈希表来存储以i结尾的最长子序列长度
     * dp[i]=dp[i-difference]+1
     *
     * @param arr
     * @param difference
     * @return
     */
    public static int efficientLongestSubsequence(int[] arr, int difference) {
        //如果数组存在多个num - difference值，那么取距离i最近的元素，map后面相同的元素会覆盖前面的元素
        //后面的元素一定是比前面的元素的最长子序列长度大的
        Map<Integer, Integer> map = new HashMap<>();
        int maxLength = 0;
        for (int num : arr) {
            map.put(num, map.getOrDefault(num - difference, 0) + 1);
            maxLength = Math.max(maxLength, map.get(num));
        }
        return maxLength;
    }

}
